package PersonStu.sanqi;

/**
 * @Author: Dijah
 * @Date: 2022/10/26 21:44
 * @Desc:
 * 背包容量为w
 * 一共有n袋零食，第i袋零食体积为v[i] > 0
 * 总体积不能超过背包容量的情况下
 * 一共有多少种零食方法？（总体积为0也是一种方法）
 *
 */
public class code_05_SnacksWays {

    public static int way1(int [] arr,int w){
       return process(arr,0,w);
    }

    /**
     *
     * @param arr ： 零食的体积
     *        index:
     * @param rest ： 背包的剩余体积
     * @return
     */
    public static int process(int [] arr,int index,int rest){
        //如果背包容量小于0，那么认为没有意义
        if (rest < 0){
            return -1;
        }
        //背包容量 >= 0

        //如果没有零食可选了
        if(index == arr.length){
            return 1;
        }

        //rest >= 0
        //当前位置上的零食 有两种选择，要和嫑

        //嫑
        int next1 = process(arr,index + 1,rest);
        //要
        int next2 = process(arr,index + 1,rest - arr[index]);
        //汇总
        return next1 + (next2 == -1 ? 0 : next2);
    }

    // 所有的货，重量和价值，都在w和v数组里
    // 为了方便，其中没有负数
    // bag背包容量，不能超过这个载重
    /**
     * 2、给定一个货物的重量和价值的数组，你装的重量不能超过这个重量。返回你能装下最大价值的价值是什么？
     * @param w
     * @param v
     * @param bag
     * @return
     */
    public static int way2(int [] w,int [] v,int bag){
        if(w == null || v == null || bag == 0){
            return 0;
        }
       return process1(w,v,0,bag);
    }

    public static int process1(int [] w,int [] v,int index,int rest){
        if(rest < 0){
            return -1;
        }
        if(index == w.length){
            return 1;
        }
        //嫑当前的位置的货物
        int p1 = process1(w,v,index + 1,rest);
        int p2 = -1;//先定义
        int p2Next = process1(w,v,index + 1,rest - w[index]);
        if(p2Next != -1){
            p2 = v[index] + p2Next;
        }
        return Math.max(p1,p2);
    }


}
